package com.ly.algorithm.leetcode.dp;

import java.util.Arrays;

/**
 * @Classname Problem718
 * @Description
 *
 * 示例：
 *
 * 输入：
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出：3
 * 解释：
 * 长度最长的公共子数组是 [3, 2, 1] 。
 *
 * @Date 2020/12/28 20:25
 * @Author 冷心影翼
 */
public class Problem718 {

	public static void main(String[] args) {
		Solution718 solution718 = new Solution718();
		System.out.println(solution718.findLength(new int[]{1, 2, 3,2, 1}, new int[]{3, 2, 1, 4, 7}));
	}

}


class Solution718 {
	public int findLength(int[] A, int[] B) {
		int n = A.length;
		int m = B.length;
		int[][] dp = new int[n+1][m+1];
		int max = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(A[i-1] == B[j-1]) {
					dp[i][j] = dp[i-1][j-1]+1;
					max = Math.max(dp[i][j],max);
				}else {
					dp[i][j] = 0;
				}
			}
		}
		return max;
	}
}